Present concepts for dynamic operation of transport networks are based either on a presumption of complete centralized control, or on distributed path provisioning operations undertaken independently and asynchronous by end-nodes, relying on local copies of global network state which are synchronized network-wide by “TE” (“traffic engineering”) type link-state updates broadcast from each node as it effects changes. The disadvantages of completely centralized control lie mainly in single-point vulnerability, signaling volumes, and scalability and are well recognized. The fully distributed peer-to-peer alternative avoids some of these drawbacks, and generally seems to be the only approach assumed for operating a dynamic survivable optical transport network.
In the view of some, however, a significant but almost always ignored issue the prospective automated WDM (or MPLS) networks have to face is hazards from network state information inconsistency, especially as network diameter increases and/or the time-scale of connections request arrivals and departures decreases. In the current thinking for such networks, connection admission control and network resource allocation functions are implemented independently at each node in a network for connections originating/terminating at that node. While this removes vulnerabilities of having a single control center and telemetry to/from that center from all network nodes, its own peer-to-peer real-time signaling intensity still grows at least as O(λn2) where n is the number of nodes in the network and λ is the arrival rate of connection requests at each node. And the database of network state, including tracking the routes of all paths in service and spare channel sharing relationships on backup paths could be growing as O(λhn4) where h is the average holding time of (protected) connections. As computational complexity arguments go, these are not extremely high growth rates for a standalone computational problems and/or database sizes, but it is hard to see why this is so often considered “scalable” in the context of a continental-scale transport network where all such signaling and database coherence is actually time-critical and mission critical because correct ongoing operation of the network relies on maintaining a globally coherent database of network state in all nodes.
In simple language, the hazard exists under asynchronous distributed provisioning because some nodes are making changes to the common state information, acting on it, and making more changes based on it. Intuitively we can see that sooner or later this will lead to problems of almost unpredictable severity. But more theoretically that intuition is confirmed in the Fischer, Lynch, Paterson theorem which states:
“The consensus problem involves an asynchronous system of processes, some of which may be unreliable. The problem is for the reliable processes to agree on a binary value. It is shown that every protocol has the possibility of non-termination, even with only one faulty process. By way of contrast, solutions are known for the synchronous case, the “Byzantine Generals” problem” (M. J. Fischer et al, “Impossibility of Distributed Consensus with One Faulty Process”, Journal of the ACM, Vol. 32, Issue 2, April 1985, p. 374-382)
Although the FLP theorem uses formal language, it tells us that if the processes involved cannot be relied upon to hold a constant value while the consensus is being attempted, a stable outcome may never be reached. But this is what engineers already know in digital logic design. We clock our logic circuits so that at significant time instants all states are frozen, allowing for propagation time through combinatorial circuits, and time for differential delays and rise/fall transition times, and so on, so that at the next clock instant, an assured correct next-state is adopted throughout the entire circuit. The hazard exists only if there is no coordination of the times at which changes and actions will be allowed and not allowed by nodes. Thus, if time synchronization is effected, we could make an entire network operate with the stability of a large clocked digital logic circuit. Thus, the role of the FLP theorem here is to explain why asynchronous operation is not assured. But conversely, it lets us see that synchronous operation can be robust in this regard—it is because no one will be trying to make changes while others are acting on the same information. In the following scheme, the equivalent of consensus can be reached because data is exchanged only during a time phase when all nodes are in agreement to temporarily not make any more changes to the data.
In the context of an optical transport network, one relatively benign outcome of temporary state inconsistency occurs if a resource is incorrectly considered not available. Then the connection admission control algorithm running at a node may reject a connection that could, in fact, have been admitted at the moment. This affects only the single connection request, however. On the other hand, if a particular resource is marked as available in the network state database of a node while it is already not available in reality, then connections may be admitted without enough resources in the network to serve them. This will usually lead to a failure of one or more conflicting path forming signaling attempts following the locally determined route choices. Normally, this too will not be a severe problem. Crank-back protocols will release the resources of the failed, but partially formed paths, and again update network state globally. End nodes may then re-attempt.
If one contemplates seriously that such networks are to (one day) operate dynamically, independently, for, say, thousands of connections a minutes, hour after hour, 24/7 for months and years, then one must be concerned about the possible outcomes of randomly arising interactions of effects from state inconsistency. It is possible to conceive worst-case event sequences that lead to the meltdown of the entire network because of repeated interacting resource allocation failures and runaway crank-back and state updating dynamics in addition to loss of network state needed to correctly activate protection arrangements. Any one such scenario may be individually improbable but one is running the experiment very often over a very long time. The interactions that led to collapse of the AT&T switching network some years were extremely improbable.
Many Internet problems are also typically understood to arise from combinations of signaling and state-update interactions. Each exact sequence of interactions that leads to a brown-out or collapse is individually very improbable, but at the large scale, happen all to often. It is not possible to give an a priori proof that a serious crash of a network will arise within so much time, given so and so size and frequency of provisioning action. Rather, the point is made for us by real-world experience with crashes in systems involving numerous asynchronously acting processes and events for which correct operation relies on the real-time coherency of a common state database. Many measures can be thought of within the existing peer-to-peer framework to reduce the likelihood of such adverse complex interactions, but no such accumulation of measures guarantees that Murphy's Law wont eventually prevail.
Ultimately, however, to motivate what follows, we do not think a reader needs to be convinces that such crashes are certain or will be noticeably frequent, only that the risk logically exists within that framework. This sets the stage for, our present thesis which is to at least propose and explain an alternate framework which is free of the hazard altogether, and provides other advantages as well.
Prior research that explicitly addresses the risk that is posed has been targeted at essentially two types of workaround so far. The first is to propose connection admission mechanisms that tolerate the inaccuracy of the network state information and alleviate its impact at the price of increased connection blocking. The second one is to drop the idea of distributed operation by introducing a central entity in charge of connection admission decisions. The latter is obviously less robust as the critical point of the system is the central entity, whose substitution may entail additional problems in case of a failure. A review of related work is presented in Zsolt Pandi, Lena Wosinska, “On temporary inconsistency of the link stata database with prompt update policies,” Proceedings ICTON 2005, Barcelona, 2005, paper TuC3.6, pp. 437-440.
Other researchers working on similar problems have recognized practical and cost-effective advantages of scheduled or batch paradigms for provisioning (Joshua Kuri, “WDM Optical Transport Networks with Scheduled Light Path Demands,” PhD Thesis, Dept. Computer Science and Networks, ENST, France Sept. 2003 (and related publications by the same group).